package leetcode.code0689;

import leetcode.helper.MaxDebug;

/**
 * 执行用时：23 ms, 在所有 Java 提交中击败了8.82%的用户
 *
 * 内存消耗：43.1 MB, 在所有 Java 提交中击败了11.76%的用户
 *
 * 通过测试用例：43 / 43
 *
 * @author CaoYu
 * @date 2021年12月8日
 * @description
 */
public class Solution5 extends S689 {

	@Override
	public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
		int Len = nums.length;
		int[] sum = new int[Len + 1];
		for (int i = 1; i <= Len; i++) {
			sum[i] = nums[i - 1] + sum[i - 1];
		}
		int[][][] dp = new int[4][Len + 1][2];
		for (int i = 1; i <= 3; i++) {
			for (int j = k * i; j <= Len; j++) {
				if (dp[i][j - 1][0] >= dp[i - 1][j - k][0] + sum[j] - sum[j - k]) {
					dp[i][j][0] = dp[i][j - 1][0];
					dp[i][j][1] = dp[i][j - 1][1];
				} else {
					dp[i][j][0] = dp[i - 1][j - k][0] + sum[j] - sum[j - k];
					dp[i][j][1] = j - k;
				}
			}
		}
		int ans1 = dp[3][Len][1];
		int ans2 = dp[2][ans1][1];
		int ans3 = dp[1][ans2][1];
		return new int[] { ans3, ans2, ans1 };
	}

	public static void main(String[] args) {
		Solution5 so = new Solution5();
		MaxDebug.debug14(so);
	}

}
